Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Ja, schön guten Morgen.

Ja, heute geht es um reguläre Ausdrücke.

Das ist ein Thema, das ist jetzt aus BFS ausgelagert hierher.

Es passt in beide Veranstaltungen.

Hier passt es deswegen hin, weil reguläre Ausdrücke eben in unser Schema passen,

das wir uns bisher angeguckt haben.

Wir programmieren, wir gucken uns dazu an, eine Syntax, und die Syntax hat eine Semantik.

Und diese Semantik unterstützt gewisse Schlussprinzipien.

Das ist das eine, und das andere ist, wir können nächste Woche, wenn wir so ein bisschen Freestyle fahren können,

weil wir nächste Woche nichts mehr machen können, was noch für die Zettel relevant ist,

können wir so ein bisschen noch mal den Bogen wieder rückwärts schlagen, zurück zur Co-Induktion.

Das ist dann eine recht hübsche Sache.

Insofern passt das hier gut rein.

Ich hatte ja an Literatur empfohlen auf der Homepage den Aho Hopcroft-Oleman.

Gut, da gibt es nun begrenzt viele Exemplare von in der Bibliothek.

Es gibt, wie ich jetzt rausgekriegt habe, eine schöne neue Quelle.

Das ist also online frei verfügbar, das heißt Lecture Notes on Regular Languages in Finite Automata.

Das ist von einem der Könige der theoretischen Informatik, Andrew Pitts, in Cambridge.

Zumindest die aktuelle Version trägt Datum 2013.

Gut, das mag nur aktualisiert sein, das weiß ich jetzt nicht genau.

Das können Sie sich da einfach runterladen.

Das ist ein, wie ich finde, schön lesbarer Text, auch relativ behutsam,

obwohl er entstammt der Informatikversion des berüchtigten Cambridge Tripos.

Ich weiß nicht, wenn Sie Mathematiker sind, ein paar Mathematiker waren immer da,

dann haben Sie vielleicht vom Cambridge Tripos gehört,

das gilt als der fortgeschrittenste mathematische Masterstudiengang überhaupt.

Davon ist das die Informatikversion und daraus stammen diese Lecture Notes.

Dafür wird da mit den Studenten, finde ich, sehr vorsichtig umgegangen.

Also das kann man gut lesen, das Ding.

Das ist also langsam und sorgfältig erklärt.

Ja, und eben kostenlos.

Ja, ich erinnere an die Teile von BFS, die man da für wissen muss.

Das ist das Folgende.

Was ist also zunächst einmal der Begriff eines nicht deterministischen endlichen Automaten mit Epsilon-Transitionen?

Hat Dirk Fanker die Epsilon- oder Lamsa-Transitionen genannt?

Weiß keiner mehr?

Dann nenne ich sie jetzt Epsilon-Transitionen.

Epsilon wie leeres Wort.

So, also ein nicht deterministischer endlicher Automat besteht aus

ein nicht deterministischer endlicher Automat, nicht? besteht aus.

Also als typischen Buchstaben nehme ich mal A wie Automat.

Der ist also übersichtlicherweise ein Fünftupel

und besteht aus folgenden Zutaten.

Das Q am Anfang, das ist zunächst einmal einfach nur eine Menge.

Ich sollte nicht vergessen, es geht um endliche Automaten, also ist die Menge endlich.

Deren Elemente wir Zustände nennen.

So, dann gibt es ein Alphabet Sigma.

Dann gibt es dieses Delta, das ist ein Alphabet Sigma.

Dann gibt es dieses Delta, das ist der komplizierte Teil des Ganzen.